Blazing Fast PSI from Improved OKVS and Subfield VOLE

发表于 2022-10-18 更新于 2023-02-19 分类于论文翻译

来自改进的 OKVS 和 VOLE 子域的极速 PSI

我们提出了新的半诚实和恶意安全的 PSI 协议，这些协议在通信和运行时间上都比之前的所有作品要好几倍。例如，我们对的半诚实协议可以在 0.37 秒内完成，而之前最好的是 2 秒（Kolesnikov 等人，CCS 2016）。在 4 个线程的情况下，这可以进一步减少到 0.16 秒，速度提高了 12 倍。同样，我们的协议发送比特，而下一个通信效率最高的协议是比特（Rindal 等人，Eurocrypt 2021）。此外，我们将我们的新技术应用于 Rindal 等人的电路 PSI 协议，运行时间提高了 6 倍。这些性能结果是通过两种类型的改进获得的。

首先是对 Rindal 等人的协议进行了优化，利用子域向量不经意线性评估。这一优化使我们的结构首次实现了的通信复杂性，其中是统计安全参数。特别是，我们的协议的通信开销不随计算安全参数乘以而扩展。

我们的第二个改进是对 OKVS 数据结构的改进，我们的协议主要依赖于这个结构。特别是，与之前的工作相比，我们的结构提高了计算和通信效率（Garimella 等人，Crypto 2021）。这些改进源于对数据结构的算法改变，以及获得其失败概率的渐进和严格的具体界限的新技术。这反过来又允许高度优化的参数选择，从而提高性能。

1 介绍

隐私集合求交集：在这项工作中，我们提出了新的改进措施，以有效地执行隐私集合求交集（PSI）。在这里，两个相互不信任的各方，分别持有一组数值、，并希望在不透露任何额外信息的情况下了解他们的集合之间的交集。特别是，拥有集合的第一方（接收方）不应该了解任何关于和的大小之外的信息。同样地，第二方（发送方）应该只学习的大小。

PSI 可以追溯到 20 世纪 80 年代 [Mea86]，最初是基于 OPRFs 和 Diffie-Hellman。事实上，几个现代协议 [CT10, IKN+20, BKM+20] 仍然是基于 [Mea86] 的协议。随着不经意传输扩展（OT extension）的发明 [IKNP03]，Schneider 等人 [PSSZ15] 开始了对一个新协议系列的研究，同时还有许多衍生协议 [PSZ14, KKRT16, RR17, OOS17, PRTY19]。这些协议以增加通信量为代价提供了更好的效率。

然而，随着 [PTY20] 和 [RS21, GPR+21] 密切相关的协议的出现，情况已经开始改变。[PRTY20] 引入了一种叫做 OKVS 的新数据结构，它提供了一种非常方便的方式来表示集合和。[PTY20] 继续将他们的 OKVS 和 [PTY19] 的 PSI 协议结合起来，得到了他们那个时代最有效的 PSI 协议之一。不久之后，[RS21] 能够观察到 OKVS 数据结构可以更有效地与向量不经意线性评估（vector oblivious linear evaluation, VOLE）相结合 [BCG+19, CRR21]，得到一个更有效的 PSI 协议。同时，[GPR+21] 提出了对 OKVS 的改进，使得 [PTY20] PSI 协议的通信开销得到改善。尽管有这些进展，[KKRT16] 的非 OKVS 协议仍然是计算效率最高的，而 [RS21] 是通信效率最高的，而 [GPR+21] 是两者之间的折中。

我们观察到，最近对 VOLE [CRR21] 和 OKVS [GPR+21] 的改进可以应用于 [RS21]。虽然这确实进一步降低了 [RS21] 的通信复杂性，但由于 [GPR+21] OKVS 数据结构的计算开销，该协议的运行时间仍然比 [KKRT16] 慢。我们将介绍对 [PRTY20, GPR+21] 的 OKVS 的重大改进，以及进一步减少 [RS21] 通信开销的新技术。

我们进一步注意到，我们的改进也转化为其他几个 PSI 相关的功能。其中最重要的一个是电路 PSI [HEK12, PRTY19, RS21]。该功能类似于普通的 PSI，除了输出是双方共享的秘密。当需要在揭示交集之前对其进行额外的加密计算时，这可能特别有用，例如，计算基数或相关值的总和 [IKN+20]。我们将我们的新技术应用于该协议，并观察到对于一百万的集合大小，运行时间和通信量分别减少 6.8 倍和 2.3 倍。

其他功能包括 [NTY21] 的多方 PSI 协议使用了 OKVS 和被称为 OPRF 或 OPPRF 的基元，可以利用我们的改进。我们把我们的工作应用于这个协议和其他许多协议作为未来的工作。

不经意键值存储 OKVS：前面提到的数据结构被称为不经意键值存储（Oblivious Key-Value Stores, OKVS），由算法和组成。将一列键值对作为输入，并返回一个编码的抽象数据结构。将这样一个数据结构和一个键作为输入，并给出一些输出。解码可以在任何密钥上调用，但如果它是在用来生成的某个上调用的，那么结果就是相应的。如果对于任何，可以表示为的线性组合，即，其中是一些公共函数，那么一个 OKVS 方案被称为是线性的。在这项工作中，我们把自己限制在线性 OKVS 方案上。

在 PaXoS [PTY20] 中，个项目被编码为一个长度为的向量。这个方案的参数是，其中只包含权重为的向量。因此，密钥的解码是，其中在 , 位置为。编码是通过对个键和所隐含的布谷鸟图进行图的遍历来进行的。

然而，这个过程很可能无法对输入的一个小子集进行编码。众所周知，这个子集的大小最多为。PaXoS 通过改变的分布来解决这个问题，使其输出一个长度为的均匀随机权重为的向量，然后是的随机采样位，即。直观地说，这允许编码器使用最后的随机位来解决与这些最后的顶点对应的方程组，而所有其他顶点则使用上述图算法解决。

[GPR+21] 提出对上述结构进行概括，使的主要部分输出权重为的向量，而不是权重为的向量。[GPR+21] 提出可以减少到，这几乎减少了 2 倍。然而，他们无法证明他们的构造在实际安全级别上的安全性。相反，他们根据经验表明，他们的结构以小但明显的概率失败，然后用递归放大技术将失败概率放大到可以忽略不计。不幸的是，这种放大法进一步增加了运行时间和紧凑性。

关于 PSI 的更多相关工作，我们参考 [RS21]，关于先前 OKVS 方案的更多细节，参考 [GPR+21]。

1.1 我们的贡献

在这项工作中，我们提出了一个改进的 OKVS 结构，并将其与 VOLE 子域一起作为一个构件，以获得迄今为止最快和最高效的 PSI 协议。

我们提出了一个框架，从理论上和具体上理解与基于布谷鸟散列的随机 OKVS 结构有关的失败概率。
在我们工作的参数和分布范围内，我们的 OKVS 编码器以压倒性的概率成为 "最优"。
有了上面的理解，我们推导出 OKVS 的构造，在紧凑性和运行时间方面大大超过了现有技术水平。
我们的 OKVS 包括对现有技术的一些优化，包括将总行权重减少 10 倍，密集列，无递归结构，以及聚类。
通过采用我们改进的 OKVS 以及我们对 [RS21] 中提出的 OPRF 和 PSI 结构的新优化，我们获得了迄今为止最高效的 PSI 协议。这些改进使我们的结构能够在 0.37 秒和 0.16 秒内完成一个项的 PSI，分别在单线程和多线程设置中。在相同的硬件上，以前最快的协议需要 2 秒，改进了 5 倍，而且需要更多的通信。
我们使用 VOLE 子域进一步优化了低通信设置的协议。我们实现了迄今为止最低的通信复杂度，用比特的通信执行个项目的 PSI，其中是统计安全参数。这个协议在运行时间上仍然非常高效。一个的 PSI 只需要比特的通信就可以完成，而之前最好的 [RS21] 是。
最后，我们将新的 OKVS 结构应用于 [PRTY19, RS21] 的电路 PSI 协议，观察到运行时间和通信量有 1.5 倍和 23 倍的改善。

1.2 概况

在第 2 节中，我们详细介绍了我们新的 OKVS 方案。将一组键值对作为输入。该算法根据键值构建一个矩阵，其中第行为某个函数。输出是一个向量，使得，即。这是通过有效地将放入下三角形矩阵（又称阶梯形矩阵）来实现的。最重要的是，我们对进行三角化的线性时间算法只对的行和列进行置换，外加少量的额外工作，因此仍然是稀疏的。一旦变成这种形式，就可以用标准的反置换算法来计算。我们还对的分布进行了一些优化，使这个过程更加有效。

在第 3 节中，我们证明了我们将置于下三角形式的技术是渐进式的最优。然后，我们利用经验和分析方法的结合，将这些渐进式的结果转化为我们构造的具体而严格的参数。与之前的一些工作不同，我们的构造可以直接扩展到任何安全级别，并适用于广泛的参数，可以以特定的应用方式进行调整。

在第 4 节，我们介绍了如何将我们的 OKVS 方案应用于 [RS21] 的 PSI 协议。从技术的角度来看，这个应用是比较直接的。然而，与现有技术相比，它立即给出了一个很大的运行时间和通信改进。这个结构同时实现了半诚实和恶意的安全。

然后，我们提出了一个优化，进一步减少了我们的 PSI 协议在半诚实环境下的通信开销。直观地说，PSI 协议的工作原理是，首先让接收方构建一个 OKVS ，这样，对于他们集合中的每个，。双方产生一个 VOLE 关联，其中 PSI 发送方持有和，接收方持有，这样，因此，由于 OKVS 是线性的，对于，我们有：发送方可以将他们的元素编码为，这将等于对于。PSI 协议通过让发送方发送给接收方，接收方将其与相交，从而推断出相交的。

原始协议要求所有这些计算都在一个大小为的场上进行。此外，为所选择的向量构建 VOLE 相关需要的通信。我们提出了优化方案，允许 VOLE 相关保持在场上（为了安全），同时将的大小减少到。特别是，我们利用了 VOLE 子域。

1.3 符号

我们用作为计算安全参数，作为统计安全参数。表示集合，是的简写。我们用箭头符号表示行向量，而元素的索引则没有箭头符号。一个集合将使用类似的符号。对于一个矩阵，我们用表示它的第行向量，表示第行和第列的元素。表示和的内积。我们用 $＝$ 表示数值相等的声明。分配被表示为，对于某个集合，符号意味着被分配到中的一个均匀的随机元素。如果一个函数是确定的，那么我们写，而如果是随机的，我们用来表示对于。

2 我们的 OKVS 构造

我们首先描述了我们的核心 OKVS 结构，它将一组键值对映射到一个向量。该结构的完整描述可以在图 1 和 A.1 节的定义中找到。

我们的算法从对一个实例密钥进行采样开始。让我们定义，其中输出一个均匀随机的（稀疏的）权重为的向量。在实践中我们将设置。输出一个短的稠密向量。的确切分布会有所不同，下面会讨论。可以被认为是一个小常数。接下来，一个矩阵被定义为：该算法将输出，使。

第一步是进行三角化。这将的行和列分别按和进行置换。特别是，它定义了两个置换矩阵，。让对应于在上应用这些置换：理想情况下，将是下三角的。然而，我们将表明，在大多数情况下，只使用排列组合是不可能实现的。相反，这些排列组合将具有这样的结构：可以被分解为，这样是一个大的下三角矩阵，其中。被称为间隙，是不能被三角化的行数。我们的想法是，然后我们可以对进行反置换，对的输入进行编码。剩下的个输入则使用不同的机制在时间内进行编码。

更详细地说，是下三角，其中。，将由产生的密集列组成。我们的三角化算法将致力于在是下三角的前提下使最小化。下一阶段将计算：其中，。对于某个，让是的（下）阶梯形矩阵。如果不具有全行等级，例如，则算法中止。否则，让其中和都是对角线上有的下三角矩阵。我们可以对进行同样的行置换：由于所有的都是下三角的，我们可以计算出：在线性时间内，通过自上而下的方式，每次解决一行，使用后置置换法。最后，该算法输出 $ᵀ$ 。

这个算法的运行时间是，再加上计算和置换的时间。因此，该算法的效率取决于三角化阶段对的最小化。此外，如果（等同于）不具有全行秩（即的行是线性依赖的），该算法就会中止。我们注意到在图 1 的第 5 步中提到了 DOKVS。这个可选的步骤对我们的电路 PSI 协议是必需的，但对 PSI 协议则不是。详见 A.2 节。

三角形算法 (Triangulation)：我们的三角形算法运行时间为。我们证明这个算法在的情况下是最优的，对于我们将关注的的小值，以压倒性的概率是 [接近] 最优。

该算法将矩阵作为输入，并输出行和列的排列组合和。这些排列组合的选择是：是近似的下三角形式，其中除了行之外，其他都是三角形。开始时，将初始化为的稀疏部分，即前列。该算法将迭代地从中移除行和列，并将它们插入到中，其中、、和的初始大小为零。

矩阵将具有不变性，即它是下三角的，在迭代，。对于一个典型的迭代，中会存在一些具有汉明权重为的列。让这一列中的一位于，即的行和列。我们的想法是，我们将从中删除（设为零）这一行，并在矩阵中加入它的混合版本，使被映射到。这样一来，的大小就增加了一个。不难验证，仍然是下三角的。

然而，在某些情况下，中不存在重量为的列。在这种情况下，我们将选择中最低的非零权重列。这些非零行中的一列将像以前一样被添加到中，而所有其他的非零行将被置换，使它们以任意的顺序被添加到中。当所有的行都从中移除时，三角化就完成了。和被定义为上述转换中隐含的排列，此外，的密集列被映射到和之间。

在第 3.3 节中，我们证明这个算法对于是最优的，对于小的也表现良好。第 3.2 节显示，的一般情况下，很可能无法以最优方式解决。对于我们的结构来说，这并不是一个问题，因为以压倒性的概率很小，例如，如第 3 节所示。

我们注意到，在我们确实有一个关于的上限的特殊情况下，有可能对进行优化的三角化。在高层次上，我们可以简单地尝试所有可能的方式，将置于上述的小于等于近似下三角形式中，即尝试所有可能的的至多行被作为间隙的一部分的集合。然而，从本质上讲，这种操作的复杂性是。我们可以做得比这好得多。我们将在后面看到，我们只需要尝试所谓的 2 核（是由定义的超图）的所有可能的最多行的集合，这一点我们将在第 3 节中定义。图 10 中描述了这种修改后的三角化算法。让表示的 2 核的大小。那么，修改后的三角形划分步骤的复杂度将是。正如我们将在第 3 节中描述的，在我们考虑的参数体系中，，，的概率非常大。事实上，根据经验，的概率极大，而是一个小常数（例如，在和之间）。上述所有事实的证明和修改后的三角形的最优性可在第 3 节找到。

的全行等级：我们算法的一个关键要求是包含一个大小为的可逆子矩阵。一个微不足道的要求是中包含的列数大于或等于。然而，即使，仍有可能不具有全行等级。决定这一点的关键因素是的分布和的大小。我们提出了两种技术来确保以压倒性的概率拥有全行等级。

二进制 ：第一种技术直接受到 [PTY20] 的启发。给定间隙大小的上限，被定义为一个均匀的函数，其中，，是统计安全参数。鉴于的分布，我们可以约束具有全行等级的概率。

推理 1：具有全行等级的概率大于等于

证明：……

域：虽然之前的方法可行，但它的缺点是大大增加了函数的权重。由于需要额外的（二进制）乘法，这带来了非同小可的性能开销。作为替代方案，我们建议将定义为一个大的域，例如阶数为，并定义其中是间隙大小的上限，，是一个随机映射。在这种情况下，将以压倒性的概率拥有全行等级。这是因为是一个随机的范德蒙矩阵（如果的值是不同的，它就有全行等级），证明有全行等级且概率极大的论证很容易延伸到证明一个固定矩阵（这里是）和的总和也会有全行等级且概率极大。

推理 2：一个随机的范德蒙德矩阵和任何固定矩阵的总和以压倒性的概率拥有全行等级。

证明：……

这种方法的主要缺点是需要在一个大的域上进行乘法运算。然而，由于硬件对乘法的支持，这种方法的性能明显优于二进制的情况。这种方法的一个限制是，值域必须是大的域上的一个向量，而二进制方法可以编码任何字符串。

参数：我们的核心结构有两个主要参数，扩展率和稀疏的函数的权重。在第 3 节，我们给出了结构的渐进分析，表明我们的算法以压倒性的概率成功，并且是线性时间。我们还提出了一个具体的分析，使我们能够精确地描述我们结构的失败概率。

一般来说，我们观察到两种现象。第一个现象被称为相变 [DM08]，在相对较小的增加过程中，间隙的预期大小从到。特别是，如果我们允许，那么可以表示为的线性函数。此外，越大，作为的函数增长得越快。我们还观察到，增加通常对扩展率有负面影响。例如，给定，，我们得到比特的安全，而，例如需要将增加到。

由此，人们可能会得出结论，总是最佳选择。然而，我们通过经验观察和分析验证，更大的可以发出以压倒性概率成功的方案，同时确保我们可以将的上限定为。特别是，对于、和的实际值，我们的方案在参数、下无法编码，而在下可以编码。这导致了最小化和整体行权重之间的权衡，我们将其留给应用来决定。

2.1 聚类

尽管上述结构在所需的参数体系中实现了线性时间编码，但在对非常大的输入长度进行编码或解码时，它有一个主要的限制，例如。大部分的内存访问实际上是对一个大小为的数组的随机访问。当足够大时，CPU 缓存不能再容纳所需的数据，必须从主内存中获取。这可能会造成运行时间的大幅减慢。

为了减轻这种影响，我们建议限制的分布：，使非零位置聚集在一起。特别是，我们重新定义为所有权重为的字符串的集合，使得对于所有，对于一些，其中是聚类的数量，是聚类的大小。也就是说，每个字符串的所有非零位置都集中在第个长度为的非重叠子串中，对于某些。然后，每个聚类可以独立地进行三角化，一次只需要处理一个聚类。在我们的实现中，我们设定，这在参数之间给出了一个很好的权衡。

虽然聚类有优势，但它会影响失败概率。为了解决这个问题，我们修改了的分布。核心问题是，每个聚类将导致一些差距，其概率基于。给出映射到任何聚类的输入项目数量的上限，就可以确定任何聚类的最大差距大小的上限。我们考虑以下两种策略。

结合 (Combined)：可以定义为一个统一的函数，其中。在这个表述中，我们利用了的额外列可以在聚类中共享的事实。由于可能比大几个系数，这将大大降低行的重量。总的来说，这种方法允许一个相对紧凑的编码，同时仍然能够进行聚类。
拆分 (Separate)：另外，可以被定义为有个聚类，这些聚类与相关联。如果被映射到第个聚类，那么应该输出一个中的均匀随机字符串，除了长度为的第个非重叠子串外，其他都是零。这样一来，我们就有效地创建了底层 OKVS 的个独立实例。这种方法与之前的方法相比略显紧凑，但允许聚类之间有更大的独立性和更低的行权重。

总的来说，聚类允许算法处理大小为的块，这些块可以比小几个数量级，这就提高了内存位置性和缓存效率。此外，比如说我们确保。这样一来，所有的内部状态值都可以存储在一个位的整数中，而不是位或位，这使得实现有更好的内存定位性，例如或的系数。

聚类自然适合于多线程的实现。项目可以被映射到聚类中，然后一个线程可以处理每个聚类而不需要昂贵的同步。所有这些优化对编码和解码都是适用的。

3 分析和参数选择

我们的 OKVS 方案的性能关键取决于的上限。我们证明了我们的算法在几个重要的情况下是最优的，否则在实践中会达到一个非常好的近似值。然后，我们对的分布进行了详细的描述。

3.1 的情况

我们从行权重的情况开始。这种情况在质量上是不同的，因为对于的实际值来说，的期望值是非零的，而且我们的算法是最优化的。

……

3.2 一般权重

……

3.3 我们算法的性能

……

3.4 结论

综上所述，我们将方程 2 中定义的的相变点和通过 f 的线性相变线的斜率定义为，其中被定义为方程 3 的右手边。定义为最小值，使，即。

在本节的最后，我们提出一个挑选参数的具体策略。特别是，给定、和：

按照方程 2 的定义计算。
计算相变线的斜率为，其中被定义为方程 3 的右边。
求解，使经过相变点的直线以的斜率通过点。
计算。

4 PSI

接下来我们谈谈我们结构的主要应用，即高效的隐私集合求交集。PSI 允许双方计算他们各自的集合、的交集，除了最终的交集外，不透露任何信息。完整的功能详见图 11。为了实现这个功能，我们利用了 [RS21] 最近的 PSI 构造，并以两种方式对其进行了修改。

用我们的新结构取代 [PRTY20] 的 OKVS。
将 [RS21] 的 PSI 协议扩展到使用 VOLE 子域 [CRR21]。

正如下面所详述的，前者的改变改善了计算开销和通信开销。特别是，当我们用新的 OKVS 实例化 [RS21] PSI 协议时，PSI 协议能够在单线程的 0.4 秒内，或 4 线程的 0.16 秒内，在消费者的笔记本电脑上执行。此外，当 VOLE 子域优化被应用时，我们能够进一步减少通信开销。

我们的出发点是 [CRR21, BCG+19] 的 VOLE [子域] 协议。图 12 中描述的 VOLE 功能包括一个发送方和接收方。发送方输出一个随机的，，而接收方则输出随机的向量，，受制于：其中是的某个扩展域。例如，，而是度 2 的扩展。为了获得 PSI，直观的想法是将 VOLE 相关解密为，其中，是一个 OKVS，对于所有解码为，其中是一个随机预言机。这个解密是主要的通信开销，需要发送，这需要发送位。

下一阶段是利用 OKVS 的线性特性。特别是，对于，我们有以下特质：拥有和的发送方能够计算右手边，而拥有的接收方能够计算左手边。接收方计算，其中，而发送方可以对任何计算。这里，是另一个随机预言机，其中。PSI 协议通过让发送方发送给接收方来完成，接收方可以从中推断出交集。完整的半诚实协议如图 9 所示。接下来我们描述一下我们的协议的几种实例化方式（通过定义、和 OKVS 参数）以获得不同的权衡。

我们的快速实例化：就运行时间而言，我们协议更有效的实例是定义和。这个变体不使用 VOLE 子域，因为它带来了轻微的运行时间开销。我们还优化了我们的 OKVS 方案，以最小化运行时间为代价，温和地增加了。特别是我们采用了方案，聚类大小为。这导致。安全性的证明见定理 3。

低通信实例化：接下来，我们的目标是以运行时间为代价，尽量减少通信开销。首先，我们将把 B 实例化为最小的场，使，把实例化为最小的扩展，使。对的大小要求是由于需要确保不会发生随机碰撞，从而导致泄露的某些信息或接收者输出一个不在中的。直观的说，这种类型的碰撞有种可能，这就要求元素的长度必须是统计安全参数加上比特。此外，我们对 OKVS 方案进行参数化，以最小化尺寸。这实际上意味着不使用聚类，结果是。安全性的证明见 C.1 节的定理 3。

恶意的实例化：对于恶意安全，我们直接使用 [RS21] 的协议与我们的 OKVS 方案。

电路 PSI：我们利用了 [RS21] 的电路 PSI 协议。我们注意到，这个协议需要 OKVS 的一个额外的不经意属性。详见 A.2 节或 [RS21]。

图 9：半诚实的协议。

半诚实的协议

参数：有两方，一个是发送方，一个是接收方，有集合，有集合，其中，。设是一个具有扩展的域，使得。令，为随机预言机。

协议：发送方输入，接收方输入后：

接收方对和进行采样，并计算，其中。
发送方发送，接收方发送到，以维度，基域和扩展。双方分别收到和。
接收方将和发送给发送方，发送方定义。
发送方将以随机顺序发送给接收方。
接收方输出。

5 评估

现在我们把注意力转移到我们结构的具体性能和与相关工作的比较上。我们的实现可以在 https://github.com/Visa-Research/volepsi 找到。综上所述，我们的构造在很大程度上超过了所有先前的工作。我们使用了 [CGS22, RR17] 的现有实现。这些协议都是在一台装有英特尔 i7 9750H 和 16GB 内存的笔记本电脑上进行基准测试。所有的构造都以比特的统计安全和比特的计算安全为目标。所有协议都在 1Gbps 的局域网环境下运行，具有亚毫秒的延迟。MT 表示每方使用四个线程。

5.1 OKVS

我们首先比较了我们的结构和 [GPR+21] 的结构的编码和解码的运行时间。如图 1 所示，我们的结构需要 653 毫秒来编码个项目，而解码只需要 54 毫秒。这比 [GPR+21] 的（）结构分别快 13 倍和 64 倍。我们将这一速度提高归因于几个因素：更小的扩展，大约 20 倍的密集列和我们更快的编码算法。我们的结构使用大小为的聚类，只需要 143 毫秒，而 [GPR+21] 的星形结构需要 4912 毫秒，速度提高了 34 倍。我们将这一额外的速度提高归因于他们的星形结构需要一个两阶段的编码，以便将成功概率放大到至少。此外，他们的结构和参数并没有针对内存效率进行优化。此外，我们的基本结构是完全安全的，因此，我们的结构允许在单程中进行编码，在聚类之间是独立的。这种独立的特性使得多线程可以在 4 个线程的情况下提供额外的 3 倍速度。

我们还考虑了我们的结构在时的运行时间，并观察到在运行时间和紧凑性方面优于它们。因此，我们得出结论，是大多数应用的正确选择。然而，我们注意到，可能有优势，因为较大的可以允许完全去除所有密集列。因此，如果需要最小化整体权重，那么或更大可能是更好的选择。

更仔细地观察 [GPR+21] 的结构，我们观察到几个不同的和值得注意的细节。首先是 [GPR+21] 的编码器采用了不同的策略：1）贪婪地遍历图形以识别 2 核，2）使用二次元时间算法解决 2 核形成的整个子系统，3）贪婪地遍历图形以解决其余的行。与我们相比，他们的构造导致了几个缺点。首先是他们直接解决由 2 核形成的子系统，为此他们需要额外的密集列。这与我们的结构相反，我们的结构是确定 2 核心的最佳子集，从而使剩余系统可以在线性时间内得到解决，这只需要密集列。例如，在的情况下，我们的结构需要两个密集列，而 [GPR+21] 提出的估计值为 60。

其次，他们的编码器需要进行两次图的遍历。第一个是需要识别 2 核，第二个是需要识别非 2 核变量应该以何种顺序来解决。虽然是线性时间，但这种类型的图遍历是一个昂贵的操作。相比之下，我们的结构允许我们维护一个有序的列表，它准确地确定了行或列应该被解决的顺序，从而减少了运行时间。

此外，[GPR+21] 让他们的构造的安全保证在很大程度上不明确。特别是，他们根据经验测量并报告了参数，的失败概率，并报告说在次试验中，只有一个实例的 2 核心的行数超过了。然后他们得出结论，在的置信度下，这个的 2 核心的上限至少以的概率成立。然而，这个概率是非常低的，因为人们可以通过分析表明，预计会有超过这么多的小结构出现。他们的论文 [GPR+21] 和实现 [GPR+] 都使用了这个似乎是错误的上界。然而，根据我们的计算，这个疏忽可能只减少了他们的统计安全性的几个比特，例如，而不是。由于 [GPR+21] 建议的扩展通常会导致比特的安全性，并继续对较小和较大的 n 值使用这个，见 [GPR+21，图 4，表 1]，情况进一步复杂。不管怎么说，这种混淆说明了对失败概率进行严格分析的必要性，就像本工作中所做的那样。

为了获得任意小的失败概率的可证明的安全性，[GPR+21] 提出了一个巧妙的放大技术，它采用了一个失败概率为的项的 OKVS 方案，并将其放大到某个小的。这有效地允许他们在的结构下实现标准的比特的安全。遗憾的是，放大法大致上要求每个项目被编码或解码两次。相比之下，我们的结构可以被调整为直接实现所需的安全级别，而没有什么开销。我们把这种放大的方案称为 " "。在时，这种结构的总体扩展率为。相比之下，我们的构造在没有聚类的情况下需要，在有聚类的情况下需要。

表 1：各种结构和输入大小的编码和解码的运行时间（ms），我们的结构的元素是，[GPR+21] 是。表示密集列是二进制的，与的默认值相反，见第二节。

表 2：我们的 PSI 协议与相关作品的性能指标比较。

5.2 PSI

如第 4 节所述，我们提出了几种 PSI 协议的实例化。第一个是我们的 "快速" 变体，它被优化为小的运行时间。第二个版本，被称为 "SD"，使用小域优化，实现了低通信开销。"MT" 表示每方使用了 4 个线程。

在所有情况下，我们的协议都大大超过了竞争对手。之前最快的半诚实协议是 [KKRT16]，它使用了一个专门的 OPRF 类型的协议。我们的协议在单线程上的速度是 3 到 8 倍。我们的协议发送的数据大约少 2 到 5 倍。此外，我们的快速协议（带聚类）可以实现多线程，这使得时的整体运行时间为 0.16 秒，速度提高了 13 倍。与我们的协议所基于的 [RS21] 相比，在时，我们观察到我们的协议提速 125 倍，我们的低通信协议提速 40 倍，同时分别减少通信开销 1.7 倍和 2.2 倍。

我们的 PSI 协议在运行时间和通信方面也超过了 [GPR+21] 几倍。[GPR+21] 是基于 [PRTY20] 的 PSI 协议，将原来的的 OKVS 方案替换为的 star 方案。最后，在恶意设置中，我们观察到我们的协议几乎没有额外的开销。因此，我们在运行时间和通信方面同样超过了所有先前的作品几倍。

我们的协议也比所谓的朴素 PSI 快，其中发送者发送其项目的哈希值。当使用 SHA256 时，我们比这个不安全的协议要快。与稍微不那么朴素的散列（AES - 散列）相比，运行时间和通信可以提高到比我们好 2 倍左右。对于不平衡的集合大小（），由于通信量与而不是成比例，朴素散列仍然是一个很大的改进。

最后，从表 2 可以看出，我们的电路 PSI 协议在运行时间和通信方面明显优于现有技术。根据我们的比较，我们的协议快 1.5 到 5 倍，发送的数据少 15 到 2 倍。[CGS22] 可以说是最有竞争力的，需要 1.8 倍的运行时间和 10 倍的通信。他们的协议使用 IKNP 来评估他们协议结尾处的比较电路以及一些优化措施。那么人们可以问，使用 SilentOT+Silver 是否可以使他们的协议与我们的协议具有竞争力。他们的渐进通信将减少到和我们一样的。然而，我们认为，由于他们的 "松弛的 OPPRF" 增加了开销，需要将每个输出与三个值进行比较，而我们的协议只与一个值进行比较，所以它仍然会具体地高。此外，在使用 Silver 的情况下，他们的运行时间可能会保持不变。

参考文献

[BCG+19] Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, Peter Rindal, and Peter Scholl. Efficient two-round OT extension and silent non-interactive secure computation. In Lorenzo Cavallaro, Johannes Kinder, XiaoFeng Wang, and Jonathan Katz, editors, Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, CCS 2019, London, UK, November 11-15, 2019, pages 291308. ACM, 2019.
[BKM+20] Prasad Buddhavarapu, Andrew Knox, Payman Mohassel, Shubho Sengupta, Erik Taubeneck, and Vlad Vlaskin. Private matching for compute. IACR Cryptol. ePrint Arch., 2020:599, 2020.
[Bol84] B ́ela Bollob ́as. The evolution of random graphs. Transactions of the American Mathematical Society, 286(1):257–274, 1984.
[CGS22] Nishanth Chandran, Divya Gupta, and Akash Shah. Circuit-psi with linear complexity via relaxed batch opprf. Proceedings on Privacy Enhancing Technologies (PETs), 2022. https://eprint.iacr.org/2021/034.
[CRR21] Geoffroy Couteau, Peter Rindal, and Srinivasan Raghuraman. Silver: Silent VOLE and oblivious transfer from hardness of decoding structured LDPC codes. In Tal Malkin and Chris Peikert, editors, Advances in Cryptology - CRYPTO 2021 - 41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16-20, 2021, Proceedings, Part III, volume 12827 of Lecture Notes in Computer Science, pages 502–534. Springer, 2021.
[CT10] Emiliano De Cristofaro and Gene Tsudik. Practical private set intersection protocols with linear complexity. In Financial Cryptography, volume 6052 of Lecture Notes in Computer Science, pages 143–159. Springer, 2010.
[DM08] Amir Dembo and Andrea Montanari. Finite size scaling for the core of large random hypergraphs. The Annals of Applied Probability, 18(5), 2008.
[ER59] Paul Erd ̈os and Alfr ́ed R ́enyi. On random graphs i. Publ. Math. Debrecen, 6:290–397, 1959.
[FK21] Alan Frieze and Michal Karo ́ nski. Introduction to random graphs, 2021.
[FKK03] Andr ́as Frank, Tam ́as Kir ́aly, and Matthias Kriesell. On decomposing a hypergraph into k connected sub-hypergraphs. Discret. Appl. Math., 131(2):373–383, 2003.
[For17] Quentin Fortier. Aspects of connectivity with matroid constraints in graphs modeling and simulation. Universit ́e Grenoble Alpes, NNT : 2017GREAM059, 2017.
[GPR+] Gayathri Garimella, Benny Pinkas, Mike Rosulek, Ni Trieu, and Avishay Yanai. OBDBasedPSI . github.com/cryptobiu/OBDBasedPSI.
[GPR+21] Gayathri Garimella, Benny Pinkas, Mike Rosulek, Ni Trieu, and Avishay Yanai. Oblivious key-value stores and amplification for private set intersection. In Tal Malkin and Chris Peikert, editors, Advances in Cryptology - CRYPTO 2021 - 41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16-20, 2021, Proceedings, Part II, volume 12826 of Lecture Notes in Computer Science, pages 395425. Springer, 2021.
[HEK12] Yan Huang, David Evans, and Jonathan Katz. Private set intersection: Are garbled circuits better than custom protocols? In 19th Annual Network and Distributed System Security Symposium, NDSS 2012, San Diego, California, USA, February 5-8, 2012. The Internet Society, 2012.
[IKN+20] Mihaela Ion, Ben Kreuter, Ahmet Erhan Nergiz, Sarvar Patel, Shobhit Saxena, Karn Seth, Mariana Raykova, David Shanahan, and Moti Yung. On deploying secure computing: Private intersection-sum-with-cardinality. In EuroS&P, pages 370–389. IEEE, 2020.
[IKNP03] Yuval Ishai, Joe Kilian, Kobbi Nissim, and Erez Petrank. Extending oblivious transfers efficiently. In CRYPTO, volume 2729 of Lecture Notes in Computer Science, pages 145–161. Springer, 2003.
[KKRT16] Vladimir Kolesnikov, Ranjit Kumaresan, Mike Rosulek, and Ni Trieu. Efficient batched oblivious PRF with applications to private set intersection. IACR Cryptol. ePrint Arch., page 799, 2016.
[Luc90] Tomasz Luczak. Component behavior near the critical point of the random graph process. Random Struct. Algorithms, 1(3):287–310, 1990.
[Mea86] Catherine A. Meadows. A more efficient cryptographic matchmaking protocol for use in the absence of a continuously available third party. In IEEE Symposium on Security and Privacy, pages 134–137. IEEE Computer Society, 1986.
[NTY21] Ofri Nevo, Ni Trieu, and Avishay Yanai. Simple, fast malicious multiparty private set intersection, 2021. https://ia.cr/2021/1221.
[OOS17] Michele Orr` u, Emmanuela Orsini, and Peter Scholl. Actively secure 1-out-of-n OT extension with application to private set intersection. In CT-RSA, volume 10159 of Lecture Notes in Computer Science, pages 381–396. Springer, 2017.
[Oxl06] J.G. Oxley. Matroid Theory. Oxford graduate texts in mathematics. Oxford University Press, 2006.
[PRTY19] Benny Pinkas, Mike Rosulek, Ni Trieu, and Avishay Yanai. Spot-light: Lightweight private set intersection from sparse OT extension. In CRYPTO (3), volume 11694 of Lecture Notes in Computer Science, pages 401–431. Springer, 2019.
[PRTY20] Benny Pinkas, Mike Rosulek, Ni Trieu, and Avishay Yanai. PSI from paxos: Fast, malicious private set intersection. In Anne Canteaut and Yuval Ishai, editors, Advances in Cryptology - EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10-14, 2020, Proceedings, Part II, volume 12106 of Lecture Notes in Computer Science, pages 739–767. Springer, 2020.
[PSSZ15] Benny Pinkas, Thomas Schneider, Gil Segev, and Michael Zohner. Phasing: Private set intersection using permutation-based hashing. In USENIX Security Symposium, pages 515–530. USENIX Association, 2015.
[PSZ14] Benny Pinkas, Thomas Schneider, and Michael Zohner. Faster private set intersection based on OT extension. In USENIX Security Symposium, pages 797–812. USENIX Association, 2014.
[PW88] Christos H. Papadimitriou and David Wolfe. The complexity of facets resolved. J. Comput. Syst. Sci., 37(1):2–13, 1988.
[RR17] Peter Rindal and Mike Rosulek. Malicious-secure private set intersection via dual execution. In ACM Conference on Computer and Communications Security, pages 1229–1242. ACM, 2017.
[RS21] Peter Rindal and Phillipp Schoppmann. VOLE-PSI: fast OPRF and circuit-psi from vector-ole. In Anne Canteaut and Fran ̧cois-Xavier Standaert, editors, Advances in Cryptology - EUROCRYPT 2021 - 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, October 17-21, 2021, Proceedings, Part II, volume 12697 of Lecture Notes in Computer Science, pages 901930. Springer, 2021.
[Wal21] Stefan Walzer. Peeling close to the orientability threshold - spatial coupling in hashingbased data structures. In D ́aniel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 2194–2211. SIAM, 2021.
[ZLS06] Jianmin Zhang, Sikun Li, and ShengYu Shen. Extracting minimum unsatisfiable cores with a greedy genetic algorithm. In Abdul Sattar and Byeong-Ho Kang, editors, AI 2006: Advances in Artificial Intelligence, 19th Australian Joint Conference on Artificial Intelligence, Hobart, Australia, December 4-8, 2006, Proceedings, volume 4304 of Lecture Notes in Computer Science, pages 847–856. Springer, 2006.